package List;

import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedList {
	private Element head;
	private int modCount;

	public int size() {
		if (head == null)
			return 0;
		Element e = head;
		int size = 1;
		while (e.next != null) {
			size++;
			e = e.next;
		}
		return size;
	}

	public LinkedList() {
		head = null;
		modCount = 0;
	}

	public int get(int index) {
		return search(index).data;
	}

	public void set(int index, int value) {
		search(index).data = value;
		modCount++;
	}

	private Element search(int index) {
		if (index < 0 || index >= size())
			throw new IndexOutOfBoundsException();
		Element e = head;
		for (int i = 0; i < index; ++i) {
			e = e.next;
		}
		return e;
	}

	private int indexOf(int value) {
		if (head == null)
			return -1;
		Element e = head;
		for (int index = 0; index < size(); index++) {
			if (e.data == value)
				return index;
			e = e.next;
		}

		return -1;
	}

	public boolean add(int value) {
		return addLast(value);
	}

	public boolean add(int index, int value) {
		Element e = search(index);
		Element element = new Element(value, e, e.previous);
		e.previous.next = element;
		e.previous = element;
		modCount++;
		return true;
	}

	public boolean addFirst(int value) {
		if (head == null) {
			head = new Element(value);

		} else {
			Element element = new Element(value, head, null);
			head.previous = element;
			head = element;
		}
		modCount++;
		return true;
	}

	public boolean addLast(int value) {
		if (head == null) {
			head = new Element(value);
		} else {
			Element e = search(size() - 1);
			Element element = new Element(value, null, e);
			e.next = element;
		}
		modCount++;
		return true;
	}

	public int remove() {
		return removeLast();
	}

	public int remove(int value) {
		int index = indexOf(value);
		if (index == -1)
			return -1;
		if (index == 0)
			return removeFirst();
		if (index == size() - 1)
			return removeLast();
		Element e = search(index);
		e.previous.next = e.next;
		e.next.previous = e.previous;
		e.next = e.previous = null;
		modCount++;
		return e.data;

	}

	public int removeFirst() {
		if (head == null)
			return -1;
		Element element = head;
		head = head.next;
		head.previous = null;
		modCount++;
		return element.data;
	}

	public int removeLast() {
		Element e = search(size() - 1);
		e.previous.next = null;
		e.previous = null;
		modCount++;
		return e.data;

	}

	public ListIterator iterator() {
		return new ListIterator();
	}
	
	public DescendingIterator descendingIterator() {
		return new DescendingIterator();
	}
	

	public int[] toArray() {
		if (size() == 0)
			return null;
		int[] result = new int[size()];
		Element e = head;
		for (int i = 0; i < size(); ++i) {
			result[i] = e.data;
			e = e.next;
		}
		return result;
	}

	public String toString() {
		return Arrays.toString(toArray());
	}

	private class ListIterator implements Iterator<Element> {
		private int index = 0;
		private Element last = head;
		private Element next = head;
		private int expectedModCount = modCount;
		private boolean flag = false;

		public boolean hasNext() {
			return index != size();
		}

		public Element next() {
			modified();
			if (index == size())
				throw new NoSuchElementException();
			flag = true;
			last = next;
			next = next.next;
			index++;
			return last;
		}

		public void remove() {
			modified();
			if (!flag)
				throw new IllegalStateException();
			LinkedList.this.remove(last.data);
			index--;
			flag = false;
			expectedModCount++;
		}

		public void modified() {
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();
		}

	}
	
	private class DescendingIterator implements Iterator<Element> {
		private int index = 0;
		private Element last = search(size()-1);
		private Element previous = search(size()-1);
		private int expectedModCount = modCount;
		private boolean flag = false;

		public boolean hasNext() {
			return index != size();
		}

		public Element next() {
			modified();
			if (index == size())
				throw new NoSuchElementException();
			flag = true;
			last = previous;
			previous = previous.previous;
			index++;
			return last;
		}

		public void remove() {
			modified();
			if (!flag)
				throw new IllegalStateException();
			LinkedList.this.remove(last.data);
			index--;
			flag = false;
			expectedModCount++;
		}

		public void modified() {
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();
		}

	}

	private class Element {
		private int data;
		private Element next;
		private Element previous;

		public Element(int data) {
			this.data = data;
		}

		public Element(int data, Element next, Element previous) {
			this.data = data;
			this.next = next;
			this.previous = previous;
		}

		public String toString() {
			return data + "";
		}

	}

}
